package lc20240522;

import lc20240521.TreeNode;

//最大路径和，动态规划解法
public class Demo4 {
    private int maxSum;

    public int maxPathSum(TreeNode root) {
        maxSum = Integer.MIN_VALUE;
        helper(root);
        return maxSum;
    }

    private int helper(TreeNode node) {
        if (node == null) {
            return 0;
        }

        int left = Math.max(helper(node.left), 0);
        int right = Math.max(helper(node.right), 0);

        int currentMaxPath = node.val + left + right;
        maxSum = Math.max(maxSum, currentMaxPath);

        return node.val + Math.max(left, right);
    }

    public static void main(String[] args) {
        Demo4 sol = new Demo4();

        // Constructing a binary tree
        //         1
        //        / \\
        //       2   3
        //      / \\
        //     4   5

        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);

        System.out.println(sol.maxPathSum(root));  // Output: 11
    }
}
